package server.io.game.util;

public class Sort_Quick extends Sort_Base
{

	private void swap(int a[], int i, int j)
	{
		int tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}

	private int partition(int a[], int p, int r)
	{
		int point = a[r];
		// 将小于等于point的元素移到左边区域
		// 将大于point的元素移到右边区域
		int index = p;
		for (int i = index; i < r; ++i)
		{
			if (a[i] - point <= 0)
			{
				swap(a, index++, i);
			}
		}
		swap(a, index, r);
		return index;
	}

	public void qsort(int a[], int p, int r)
	{
		if (p < r)
		{
			// 确定拆分点，并对数组元素进行移动
			// 这是快速排序算法的关键步骤
			int q = partition(a, p, r);
			// 对左半段排序
			qsort(a, p, q - 1);
			// 对右半段排序
			qsort(a, q + 1, r);
		}
	}
}